package com.leetcode.partition1;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/29 8:49
 */
public class LC45跳跃游戏2 {

    public static int jump(int[] nums) {
        if (nums.length <= 1) return 0;
        return dynamicProgramming(nums);
    }

    public static void main(String[] args) {
//        int[] nums = {2, 3, 1, 1, 4};
        int[] nums = {2, 3, 1, 1, 2, 1, 4, 2};
//        int[] nums = {2, 3, 0, 1, 2, 1, 1};
//        int[] nums = {1, 2, 3};
        System.out.println(jump(nums));
    }

    private static int dynamicProgramming(int[] nums) {
        int[] dp = new int[nums.length];
        //初始化，对于nums数组，最多的步数就是需要一步一步的跳，所以最大值不会超过nums.length-1
        Arrays.fill(dp, nums.length - 1);
        dp[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length && j <= i + nums[i]; j++) {     //[i, j]，从i开始能够1步到达的位置，j<=i+nums[i]保证在i位置能够一步到达j
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[dp.length - 1];
    }

    private static int greedy(int[] nums) {
        int end = 0, maxPosition = 0, answer = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                System.out.println(maxPosition);
                end = maxPosition;
                answer++;
            }
        }
        return answer;
    }
}
